|
Turing's proof is a proof by Alan Turing, first published in January 1937 with the title ''On Computable Numbers, With an Application to the Entscheidungsproblem''. It was the second proof of the assertion (Alonzo Church's proof was first) that some decision problems are "undecidable": there is no single algorithm that infallibly gives a correct "yes" or "no" answer to each instance of the problem. In his own words: "...what I shall prove is quite different from the well-known results of Gödel ... I shall now show that there is no general method which tells whether a given formula U is provable in K (Mathematica )..." (Undecidable p. 145). Turing preceded this proof with two others. The second and third both rely on the first. All rely on his development of type-writer-like "computing machines" that obey a simple set of rules and his subsequent development of a "universal computing machine". == Richard's paradox == In 1905 Jules Richard presented this profound paradox. Alan Turing's first proof constructs this paradox with his so-called computing machine and proves that this machine cannot answer a simple question: will this machine be able to determine if ''any'' computing machine (including itself) will become trapped in an unproductive "infinite loop" (i.e. it fails to continue its computation of the diagonal number). A succinct definition of Richard's paradox is found in Whitehead and Russell's ''Principia Mathematica'': :Richard's paradox... is as follows. Consider all decimals that can be defined by means of a finite number of words; let E be the class of such decimals. Then E has (an infinity of ) terms; hence its members can be ordered as the 1st, 2nd, 3rd, ... Let N be a number defined as follows (& Russell now employ the Cantor diagonal method ); If the nth figure in the nth decimal is p, let the nth figure in N be p+1 (or 0, if p = 9). Then N is different from all the members of E, since, whatever finite value n may have, the nth figure in N is different from the nth figure in the nth of the decimals composing E, and therefore N is different from the nth decimal. Nevertheless we have defined N in a finite number of words (this very word-definition just above! ) and therefore N ought to be a member of E. Thus N both is and is not a member of E (''Principia Mathematica'', 2nd edition 1927, p. 61). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Turing's proof」の詳細全文を読む スポンサード リンク
|